#pragma once
#include <iostream>
#include <stack>
using namespace std;

template<class K>
struct BSTreeNode 
{
  BSTreeNode(K& key)
    :_left(nullptr)
    ,_right(nullptr)
    ,_key(key)
  {}
  BSTreeNode* _left;
  BSTreeNode* _right;
  K _key;
};

template<class K>
class BSTree 
{
  typedef BSTreeNode<K> Node;
  public:
  BSTree()
    :_root(nullptr)
  {}

  bool Insert(K& key)
  {
    if (_root == nullptr)
    {
      _root = new Node(key);
      return true;
    }
    Node* cur = _root;
    Node* parent = nullptr;
    while (cur)
    {
      if (key > cur->_key)
      {
        parent = cur;
        cur = cur->_right;
      }
      else if (key < cur->_key)
      {
        parent = cur;
        cur = cur->_left;
      }
      else 
        return false;
    }
    cur = new Node(key);
    if (key > parent->_key)
      parent->_right = cur;
    else 
      parent->_left = cur;

  }

  bool Find(K& key)
  {
    Node* cur = _root;
    while (cur)
    {
      if (key > cur->_key)
      {
        cur = cur->_right;
      }
      else if (key < cur->_key)
      {
        cur = cur ->_left;
      }
      else 
      {
        return true;
      }
    }
    return false;
  }

  //void InOrderR()
  //{
  //  _InOrder(_root);
  //}

  //void _InOrderR(Node* root)
  //{
  //  if (root == nullptr)
  //  {
  //    return;
  //  }
  //  _InOrderR(root->_left);
  //  cout << root->_key << " ";
  //  _InOrderR(root->_right);
  //}
  
  void InOrder()
  {
    stack<Node*> st;
    Node* p = _root;
    do
    {
      while (p)
      {
        st.push(p);
        p = p->_left;
      }
      p = st.top();
      st.pop();
      cout << p->_key << " ";
      if (p->_right)
        p = p->_right;
      else 
        p = nullptr;
    }while(p || !st.empty());
    cout << endl;
  }


  bool Erase(const K& key)
  {
    Node* cur = _root;
    Node* parent = nullptr;
    while (cur)
    {
      if (key > cur->_key)
      {
        parent = cur;
        cur = cur->_right;
      }
      else if (key < cur->_key)
      {
        parent = cur;
        cur = cur->_left;
      }
      else 
      {
        if (cur->_left == nullptr)
        {
          if (parent == nullptr)
          {
            _root = _root->_right;
          }
          else 
          {
            if (parent->_left == cur)
            {
              parent->_left = cur->_right;
            }
            else 
            {
              parent->_right = cur->_right;
            }
          }
          delete cur;
          cur = nullptr;
          return true;
        }
        else if (cur->_right == nullptr)
        {
          if (parent == nullptr)
          {
            _root = _root->_left;
          }
          else 
          {
            if (parent->_left == cur)
            {
              parent->_left = cur->_left;
            }
            else 
            {
              parent->_right = cur->_left;
            }
          }
          delete cur;
          cur = nullptr;
          return true;
        }
        else 
        {
          Node* prev = cur;
          Node* left_max = cur->_left;
          while (left_max->_right)
          {
            prev = left_max;
            left_max = left_max->_right;
          }
          cur->_key = left_max->_key;
          if (prev->_right == left_max)
          {
            prev->_right = left_max->_left;
          }
          else 
          {
            prev->_left = left_max->_left;
          }
          delete left_max;
          left_max = nullptr;
          return true;
        }
      }
    }
    return false;
  }
  private:
    Node* _root;
};



